/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} list1
 * @param {ListNode} list2
 * @return {ListNode} 
 */

// 合并字符串并要求返回的是原先两个链表
// var mergeTwoLists = function (list1, list2) {
//   if (list1 == null) return list2
//   if (list2 == null) return list1
//   let head = new ListNode(0, null);
//   let first = head;
//   while (list1 !== null && list2 !== null) {
//     if (list1.val < list2.val) {
//       head.next = list1;
//       list1 = list.next;
//     } else {
//       head.next = list2;
//       lsit2 = list2.next;
//     }
//     head = head.next;
//   }
//   if (list1 !== null) {
//     head.next = list1;
//   }
//   if (list2 !== null) {
//     head.next = list2
//   }
//   return first.next
// }

var mergeTwoLists = function (list1, list2) {
  //递归退出的条件
  if (list1 == null) return list2
  if (list2 == null) return list1
  //比较头节点大小
  if (list1.val < list2.val) {
    list1.next = mergeTwoLists(list1.next, list2)
    return list1
  } else {
    list2.next = mergeTwoLists(list1.next, list1)
    return list2
  }
}